# 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 
# 
#  
# 
#  示例 1： 
# 
#  
# 
#  
# 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
# 输出：6
# 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
#  
# 
#  示例 2： 
# 
#  
# 输入：height = [4,2,0,3,2,5]
# 输出：9
#  
# 
#  
# 
#  提示： 
# 
#  
#  n == height.length 
#  1 <= n <= 2 * 104 
#  0 <= height[i] <= 105 
#  
#  Related Topics 栈 数组 双指针 动态规划 单调栈 
#  👍 2758 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        n = len(height)
        left_max = [height[0]] + [0] * n
        for i in range(1, n):
            left_max[i] = max(left_max[i-1], height[i])
        right_max = [0] * n + [height[n-1]]
        for i in range(n-1, -1, -1):
            right_max[i] = max(right_max[i+1], height[i])
        ans = sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))
        return ans


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 动态规划
# i 位置能存的水 = min(左最大高度, 右最大高度) - height[i]
# 正向遍历数组, 获取每个元素左侧元素最大值 leftMax[i] = max(leftMax[i-1], height[i])
# 反向遍历数组, 获取每个元素右侧元素最大值 rightMax[i] = max(rightMax[i+1], height[i])
#     def trap(self, height: List[int]) -> int:
#         if not height:
#             return 0
#         n = len(height)
#         # 初始化leftMax
#         left_max = [height[0]] + [0] * (n - 1)
#         for i in range(1, n):
#             left_max[i] = max(left_max[i - 1], height[i])
#         # 初始化 right_max
#         right_max = [0] * (n - 1) + [height[n - 1]]
#         for i in range(n - 2, -1, -1):
#             right_max[i] = max(right_max[i + 1], height[i])
#         ans = sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))
#         return ans
# 双指针优化
# height[left] < height[right] 则 left_max < right_max
#
# max_left[i] = max(max_left[i-1], height[i]) 即 i 是 i -1 更新过来的
# 同理, right j 是 j + 1 更新过来的
# 所以只要 height[i] < height[j] 则

if __name__ == '__main__':
    s = Solution()
    h1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    r1 = s.trap(h1)
    e1 = 6
    assert r1 == e1, r1
